package com.zp.self.module.level_4_算法练习.算法.深度优先搜索.回溯;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * @author By ZengPeng
 */
public class 力扣_131_分割回文串 {
    //测试
    public static void main(String[] args) {

        System.out.println(new 力扣_131_分割回文串().partition("aab"));
    }

    /**
    题目：给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
     回文串 是正着读和反着读都一样的字符串。

     示例 1：
     输入：s = "aab"
     输出：[["a","a","b"],["aa","b"]]

     示例 2：
     输入：s = "a"
     输出：[["a"]]

    分析：【PR 💜💜💜】
       1.回溯法+双指针：记录节下标，一个向下，并回溯
                --执行用时：9 ms, 在所有 Java 提交中击败了36.39%的用户
                优化：A 不使用deque,而是使用List   快了1ms
                      B 不使用char[],而是使用String.substring()   快了2ms   ....【我不理解！】？？？？？离谱
                    --执行用时：6 ms, 在所有 Java 提交中击败了99.23%的用户

    边界值 & 注意点：
       1.
     **/
    public List<List<String>> partition(String s) {
        List<List<String>> res =new ArrayList<>();
        List<String> path = new ArrayList<>();
//        char[] chars = s.toCharArray(); //  B 不使用char[],而是使用String.substring()   快了2ms   ....我不理解！
        dfs(s,0,path,res);
        return res;
    }

    private void dfs(String s, int index, List<String> path, List<List<String>> res) {
      if(index==s.length())
          res.add(new ArrayList<>(path));
      else {
          for (int i = index; i < s.length(); i++) {
              if(isPalindromeString(s,index,i)){
                  path.add(s.substring(index,i+1));
                  dfs(s,i+1,path,res);
                  path.remove(path.size()-1);
              }
          }
      }
    }

    private boolean isPalindromeString(String s, int left, int right) {
        while (left<right){
            if(s.charAt(left++)!=s.charAt(right--))return false;
        }
        return true;
    }
}
